package com.base.dynamicprograming;

import java.util.ArrayList;
import java.util.Iterator;

/**
 * 42. 接雨水
 *
 * @author leon
 * @date 2021年12月06日 21:04
 */
public class Trap {


    public int trap(int[] height) {
        int n = height.length;
        if(n == 1){
            return 0;
        }
        int[] maxLeft = new int[n];
        int[] maxRight = new int[n];
        maxLeft[0] = height[0];
        for(int i = 1;i<n;i++){
            maxLeft[i] = Math.max(maxLeft[i-1],height[i]);
        }
        maxRight[n-1] = height[n-1];
        for(int i = n-2;i>=0;i--){
            maxRight[i] = Math.max(maxRight[i+1],height[i]);
        }

        int res = 0;
        for(int i=0;i<n;i++){
            res += (Math.min(maxLeft[i],maxRight[i]) - height[i]);
        }
        return res;
    }


    public static void main(String[] args) {
        System.out.println(new Trap().trap(new int[]{5,4,1,2}));
    }
}
